package sort;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Random;

/**
 *  基于比较排序算法 + 部分优化 大合集!
 */
public class Sort {

    private static void swap(int[] arr, int j, int i) {
        if(i == j) return ; // (这个坑要注意!)
        arr[i] ^= arr[j];
        arr[j] ^= arr[i];
        arr[i] ^= arr[j];
    }


    /**
     *  冒泡排序思路
     *  每次将最大的元素放到最后
     * @param arr
     *  优化思路:
     *   有序性传递特征:
     *      连续相邻的数字会发生比较,一旦两个连续数字种存在不有序情况就会导致交换的发生!
     *      当本次冒泡未发生交换就能确定上一次冒泡,已经将排序完成!
     */
    public static void bubbleSort(int[] arr){
        for(int i = 0; i < arr.length - 1; i++){
            boolean sorted = true; // 开始假设待排序区间是有序的!
            for(int j = 0; j < arr.length - i - 1; j++){
                if(arr[j] > arr[j+1]){
                    sorted = false;
                    swap(arr,j,j+1);
                }
            }
            if(sorted) return;
        }
    }






    /**
     *  选择排序, 思路 :
     *      每次从待排序区间中找到最大的放到排序区间的最前面
     *      使得排序区间 范围 +1 未排序区间范围 -1 直到未排序区间被完全占领!
     *
     *      还可以考虑 :
     *      每次从待排序区间种找到最小的值,放到排序区间的最后面
     *
     * @param arr
     */
    public static void selectSort(int[] arr){
        Random random = new Random();
        int selectAOrB = random.nextInt();
        if((selectAOrB&1) == 0) selectSortA(arr);
        else selectSortB(arr);
    }


    public static void selectSortA(int[] arr){

        for(int i = 0; i < arr.length - 1; i++){
            /**
             *  从无序区间里找到,最大值放到排序区间的的最前面
             *  无序区间 [0,arr.length - i - 1]
             *  排序区间 (arr.length - i - 1,arr.length)
             */

            int maxIndex = 0;
            for(int j = 1; j < arr.length - i; j++){
                if(arr[j] > arr[maxIndex]){
                    maxIndex = j;
                }
            }

            swap(arr,arr.length - i - 1,maxIndex);

        }
    }


    public static void selectSortB(int[] arr){
        for(int i = 0; i < arr.length - 1; i++){
            /**
             *  从无序区间种找到最小值,把他放到有序区间的最末尾
             *  有序区间 [0,i)
             *  无序区间 [i,arr.length)
             */
            int minIndex = arr.length - 1;

            for(int j = arr.length - 2; j >= i; j--){

                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }

            swap(arr,minIndex,i);
        }
    }


    /**
     *  插入排序 思路 :
     *      思路每次从无序区间种取出一个数,
     *      在有序区间种找到合适这个数的位置!
     * @param arr
     */
    public static void insertSort(int[] arr){
        /**
         *  有序区间 [0,i)
         *  无序区间 [i,arr.length)
         */
       for(int i = 1; i < arr.length; i++){
           int sortIndex = i-1; // 有序区间右边界
           int val = arr[i];

           while(sortIndex >= 0 && arr[sortIndex] > val){// 这里是稳定的
               arr[sortIndex + 1] = arr[sortIndex];
               sortIndex--;
               // 有查找效率 用二分查找找到位置
               // 但是避免不了 将元素后移 所以一般不用
           } // 要么 == -1 要么到了合适的位置.

           // 将元素插入到有序区间的合适位置!
           arr[sortIndex+1] = val;
       }
    }


    /**
     *  希尔排序 思路:
     *      利用了插入排序的思路 (插入优点 : 在数据规模不大 或者 数组相对有序的情况下,效率极高)
     *      将 数组逻辑上分成很多组 再将这么多组进行插入排序,最终达到相对有序,提升效率!
     *
     * @param arr
     */
    public static void shellSort(int[] arr){
        int gap = (arr.length>>1);
        // 分组插排
        while(gap > 0){
            insertByGap(arr, gap);
            gap >>= 1;
        }
    }

    private static void insertByGap(int[] arr, int gap) {
        for(int i = gap; i < arr.length; i += gap){
            int sortIndex = i - gap;
            int val = arr[i];
            while(sortIndex >= 0 && arr[sortIndex] > val){
                arr[sortIndex + gap] = arr[sortIndex];
                sortIndex -= gap;
            }
            arr[sortIndex + gap] = val;
        }
    }


    /**
     *  堆排序 思路:
     *      将数组建立成堆,
     *      再进行逻辑上删除堆顶(即将无序区间中的第一个数放到有序区间的末尾!)
     *
     * @param arr
     */
    public static void heapSort(int[] arr){ // 堆排序
        // 将数组建立成堆!
        for(int i = (arr.length -1)/ 2 ; i >= 0; i--){
            adjustDown(arr,i,arr.length);
        }

        /**
         *  逻辑删除堆顶部!
         *  有序区间 [len - i + 1,arr.length)
         *  无序区间 [0,len -i)
         */
        int len = arr.length - 1;
        for(int i = 0; i < len; i++){
            swap(arr,0,len - i);
            adjustDown(arr,0,len - i);
        }
    }
    // 堆的相下调整 [parent,length)
    private static void  adjustDown(int[] arr,int parent,int length){
        int child = parent * 2 + 1;
        while(child < length){
            if(child + 1 < length && arr[child] < arr[child + 1]){
                child++;
            }
            if(arr[parent] >= arr[child]){
               break;
            }
            swap(arr,parent,child);
            parent = child;
            child = child * 2 + 1;
        }
    }


    /**
     *  快速排序 思路 :
     *      选择一个基准值pivot找到基准值排序后应该在的位置!
     *      即 pivot 左边 <= pivot
     *               右边 >= pivot
     *
     *      下面是递归版本 :
     * @param arr
     */
    public static void quicklySort(int[] arr){
        quicklySortRange(arr,0,arr.length - 1);
    }

    private static void quicklySortRange(int[] arr, int from, int to) {
        if(to - from + 1 <= 1) return;
        Result result = partitionThree(arr, from, to);
        quicklySortRange(arr,from,result.small_end);
        quicklySortRange(arr,result.big_begin,to);
    }


    /**
     *  快速排序 优化:
     *          当数据范围不大的时候,插入排序的效率远远高于快速排序
     *          可以在将无序区间分割的足够小的时候 用插入排序来优化
     */
    static int bound = 20; // 约定当数据规模<= 20 用插入排序优化!
    private static void quicklySortRangeOpt(int[] arr,int from,int to){
        if(to - from + 1 <= bound) {
            insertSortByBound(arr,from,to);
            return ;
        }
        Result result = partitionThree(arr, from, to);
        quicklySortRangeOpt(arr,from,result.small_end);
        quicklySortRangeOpt(arr,result.big_begin,to);
    }

    private static void insertSortByBound(int[] arr, int from, int to) {
        for(int i = from; i < to; i++){
            int sorted_index = i-1;
            int target = arr[i];
            while(sorted_index >= from && target < arr[sorted_index]){
                sorted_index--;
            }
            arr[sorted_index + 1] = target;
        }
    }


    /**
     *
     * 将区间分为两块
     *          [<= pivot] pivot [>= pivot]
     *          [0,left) <= pivot 区间
     *          [right,arr.length) >= pivot 区间
     *          [left,right] 未参与比较区间!
     * @param arr
     * @param from
     * @param to
     * @return
     */
    private static int partition(int[] arr,int from,int to){

        /**
         *  取区间最右边的作为基准值,
         *  将被取过的位置想想成为一个坑
         *  当找的可以填充坑的元素就把这个元素填上那个坑
         *  此时这个元素所在的位置就成为了新的坑
         *  一致到区间比较完毕
         *  这个坑的位置就是基准值的位置
         *
         *  所以这也算是一种优化
         */
        int pivot = arr[to];
        int left = from;
        int right = to;
        while(left < right){ // 未参与比较区间
            while(left < right && arr[left] < pivot){
                left++;
            }
            arr[right] = arr[left]; // 填坑!
            while(left < right && arr[right] > pivot){
                right--;
            }
            arr[left] = arr[right]; // 填坑!
        }
        arr[left] = pivot;
        return  left;
    }


    /**
     *  另外一种 区间划分(两块):
     *      [less_begin,less_end) <= pivot;
     *      [less_end,big_end) >= pivot;
     *      [big_end,to) 未参与比较
     *      [to,to] pivot
     * @param arr
     * @param from
     * @param to
     * @return
     */
    private static int partitionOther(int[] arr,int from,int to){
        int pivot = arr[to];
        int less_begin = from;
        int less_end = from;
        int big_end = from;
        /**
         * 当一块的范围被确定了
         * 另外一块的范围也就有了
         * 所谓 非黑即白 就是这个道理!
         */
        for(int i = big_end; i < to; i++){
            if(arr[i] < pivot){ // 属于<= pivot 区域的!
                swap(arr,i,less_end);
                less_end++;
            }
        }
        arr[to] = arr[less_end];
        arr[less_end] = pivot;
        return less_end;
    }



    static class Result{
        public int small_end;
        public int big_begin;
    }
    /**
     * 把区间分成 三块!
     * [from,small_end) <  pivot;
     * [small_end,equal_end) == pivot;
     * (big_begin,to] > pivot;
     * @param arr
     * @param from
     * @param to
     * @return
     */
    private static Result partitionThree(int[] arr,int from,int to){
        int small_end = from;
        int equal_end = from;
        int big_begin = to;
        int pivot = arr[to];

        while(big_begin - equal_end + 1 > 0){ // 未排序区间大小
            if(arr[equal_end] > pivot){
                swap(arr,equal_end,big_begin);
                big_begin--;
            }else if(arr[equal_end] == pivot){
                equal_end++;
            }else {
                swap(arr, small_end, equal_end);
                small_end++;
                equal_end++;
            }
        }

        Result result = new Result();
        result.small_end = small_end - 1;
        result.big_begin = equal_end;
        return result;
    }


    /**
     *  快速 排序非递归实现!
     * @param arr
     * @param from
     * @param to
     */
    public static void quicklySortRangeNo(int[] arr,int from,int to){
        Deque<int[]> stack = new LinkedList<>();
        stack.push(new int[]{from,to});
        while(!stack.isEmpty()){
            int[] pop = stack.pop();
            Result result = partitionThree(arr, pop[0], pop[1]);
            stack.push(new int[]{pop[0],result.small_end});
            stack.push(new int[]{result.big_begin,pop[1]});
        }
        return ;
    }


    /**
     *  归并排序 :
     *      将两个有序区间进行合并,得到一个更大的有序区间!
     * @param arr
     */
    public static void mergeSort(int[] arr){
        mergeSortRange(arr,0,arr.length);
    }

    private static void mergeSortRange(int[] arr, int from, int to) {
        if(to - from <= 1) return ; //区间内只有一个元素 当然是有序区间!

        int mid = from + ((to - from)>>1);
        // 将区间分开并使得每个区间有序
        mergeSortRange(arr,from,mid);
        mergeSortRange(arr,mid,to);
        // 合并两个有序区间 [from,mid) , [mid,to);
        merge(arr,from,mid,to);
    }

    private static void merge(int[] arr, int from, int mid, int to) {
        int left = from;
        int right = to;
        int[] other = new int[to - from];
        int dest = 0;
        // 只要左右两个小区间还有元素要参与比较
        while (left < mid && right < to) {
            if (arr[left] <= arr[right]) {
                other[dest++] = arr[left++];
            } else {
                other[dest++] = arr[right++];
            }
        }
        // 其中一个区间的元素取完了，另一个区间里一定还有元素，再把剩余的元素，统统放入 other
        // 看起来左右两个都写了，但执行起来的时候一定只有一个会执行
        while (left < mid) {
            other[dest++] = arr[left++];
        }
        while (right < to) {
            other[dest++] = arr[right++];
        }

        // 把 other 中的有序元素，复制回 array 中，要注意下标的问题
        for (int i = 0; i < to - from; i++) {
            arr[from + i] = other[i];     // array 下标的基准是从 [from] 开始，other 下标的基准是从 [0] 开始
            // offset(偏移）是一致的，都是 i
        }

    }

}
